package com.剑指offer一;

/**
 * 剑指 Offer 24. 反转链表
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 *
 * @author leon
 * @date 2021年12月15日 18:45
 */
public class ReverseList {
    /**
     * 方法一，头插法
     */
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode moveNode = head;
        while (moveNode!=null){
            ListNode node = moveNode;
            moveNode = moveNode.next;
            node.next = dummy.next;
            dummy.next = node;
        }
        return dummy.next;
    }

    /**
     * 递归
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head){
        if(head == null || head.next==null){
            return head;
        }
        // 返回的是最后一个结点的值，也就是反转后的第一个结点值
        ListNode node = reverseList1(head.next);
        // 将后结点指向前结点
        head.next.next = head;
        // 将前结点到 后结点的值断掉
        head.next = null;
        return node;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
